package com.congee02;

import java.util.*;

/**
 * https://leetcode.cn/problems/linked-list-random-node/
 */
public class RandomList1 {

    List<ListNode> indexes = new ArrayList<>();

    final static int BITS = 3;
    final static int N = 1 << BITS;
    int size;
    final Random R = new Random();

    public RandomList1(ListNode head) {
        int counter = 0;
        int cnt = 0;
        ListNode p = head;
        while (p != null) {
            if ((counter & (N - 1)) == 0) {
                indexes.add(p);
            }
            cnt ++;
            counter ++;
            p = p.next;
        }
        size = cnt;
    }

    public int getRandom() {
        int random = R.nextInt(size);
        int indexIndex = random >>> BITS;
        int offset = random & (N - 1);
        ListNode p = indexes.get(indexIndex);
        for (int i = 0; i < offset; i++) {
            p = p.next;
        }
        return p.val;
    }

}
